这道题没有想象中的那么难，只不过板子P4718 【模板】Pollard-Rho算法是黑的（为什么这道题是紫的）
既然题目保证为两质数乘积。我们可以用
求出。
P3704 [SDOI2017]数字表格
前置知识：莫比乌斯反演，数论分块
题意
P2922 秘密消息
这道题还是Trie树的板题，先将n个信息插入字典树中，对于查询的密码，在字典树中查询即可。
插入很好办，我们现在来讨论查询操作。我们记s1为任意一个信息，s2是待匹配的密码。tot[u]表示有多少个字符串经过点u，fin[u]表示有多少个字符串以点u结尾。
那么会出现三种情况：
P3119 Grass Cownoisseur
我们应该用Tarjan缩点，将原图变为GAD图，同时记录每个强连通分量的节点个数，记为num[i]。
因为起点终点都是1，所以路径一定是一个环。我们可以处理出1到所有点的距离，存在dis1中（跑正图）和所有点到1的距离存在dis2中（跑反图）。注意，如果走不到就设为极小值。最短路跑的是点权，其实和边权差不多。
题目说可以逆向走一条有向边，我们设该边起点为u，终点为v，那么，答案就应为num[belong[1]]+max(dis1[v]+dis2[u])。
CF794F Leha and security system
一道神奇的线段树...
题目要求区间修改，区间查询，很容易想到线段树，但是怎么维护每一位数字呢？
显然，我们将每位拆分，对于每一个数字维护他的贡献，如 1221123 中 1 的贡献为 1001100 , 2 的贡献为 110010。于是，我们需要10棵线段树，维护0−9的贡献。
0%
